﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._30
{
    public class Leetcode21
    {
        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }
        public void Test()
        {
            try
            {
                ListNode l1 = new ListNode(1);

                l1.next = new ListNode(2);

                l1.next.next = new ListNode(3);

                ListNode l2 = new ListNode(2);
                var a = MergeTwoLists(l1, l2);
            }
            catch (Exception ex)
            { }
        }
        /*
         21. Merge Two Sorted Lists 

        Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
         */
        public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if (l1 == null)
                return l2;
            if (l2 == null)
                return l1;

            ListNode l1NextNode = l1;
            ListNode l2NextNode = l2;
            ListNode newListNode = null, tempNewListNodeNext = null;
            if (l1NextNode.val < l2NextNode.val)
            {
                newListNode = new ListNode(l1NextNode.val);
                l1NextNode = l1NextNode.next;
            }
            else
            {
                newListNode = new ListNode(l2NextNode.val);
                l2NextNode = l2NextNode.next;
            }
            tempNewListNodeNext = newListNode;

            while (l1NextNode != null || l2NextNode != null)
            {
                if (l1NextNode == null)
                {
                    tempNewListNodeNext.next = l2NextNode;
                    break;
                }
                if (l2NextNode == null)
                {
                    tempNewListNodeNext.next = l1NextNode;
                    break;
                }

                if (l1NextNode.val < l2NextNode.val)
                {
                    tempNewListNodeNext.next = new ListNode(l1NextNode.val);
                    tempNewListNodeNext = tempNewListNodeNext.next;
                    l1NextNode = l1NextNode.next;
                }
                else
                {
                    tempNewListNodeNext.next = new ListNode(l2NextNode.val);
                    tempNewListNodeNext = tempNewListNodeNext.next;
                    l2NextNode = l2NextNode.next;
                }
            }
            return newListNode;
        }
    }

}
